1. Field of the Invention
The invention relates to digital systems and more particularly to FIFOs (First-In First-Out buffers).
2. Description of the Relevant Art
FIFOs are First-In First-Out buffers that act as elastic buffers between two synchronous or asynchronous systems. A FIFO includes an area of storage which temporarily holds data from one digital system that will be subsequently delivered to a second digital system. FIFOs have applications, for example, within networks where data must be transferred from a digital system operating at a first frequency to a digital system operating at a second frequency. In such cases, the FIFO supports efficient utilization of the digital systems since the system transmitting data does not have to wait for the receiving system to accept the data.
FIG. 1 shows an area of storage within a typical FIFO. In this particular example, the area of storage consists of 4K bytes of memory locations, each nine-bits wide.
When receiving data, a technique known as circular buffering is commonly implemented. The basic strategy, as shown in FIG. 2, is to give the appearance that the buffer is organized in a circle, with data "wrapping around" when received. This appearance of circular organization is accomplished by using two pointers, write pointer and read pointer, associated with the buffer. Initially, when no data is contained in the buffer, the write pointer and the read pointer both point to the starting storage location labeled START. Data is received at an input bus and consequently fills the buffer starting from START and incrementing the write pointer. When data is taken from the buffer at an output bus, the read pointer increments. When the last storage location (END) of the buffer has been filled, the write pointer is reset to START and subsequent data will wrap around to the start of the buffer. Similarly, when the read pointer reaches END, it is reset to START and also wraps around.
Control circuitry and flags are used to prevent reading of storage locations which do not contain valid data and to prevent writing into storage locations which contain data not yet read or "consumed." It is evident that these conditions may occur if the READ pointer equals or exceeds the WRITE pointer.
FIG. 3 shows a functional block diagram of a basic FIFO circuit. The basic FIFO comprises a dual port memory 10, write pointer logic 11, read pointer logic 12, three-state buffers 13, a write control 14, a read control 15, flag logic 16, and reset logic 17. Memory 10 includes 4096 (4K) memory locations, each nine bits wide, an address decoder, write circuitry, and a sense amplifier.
During operation, data is sequentially loaded into memory 10 through data input lines D.sub.0 -D.sub.8. Write pointer 11 points to the address of the location in memory 10 to which each byte of input data is loaded.
Data is sequentially output from memory 10 through three-state buffers 13. Read pointer 12 points to the address of the location in memory 10 which contains the byte of data which is read out at the output lines of three-state buffers 13.
Write control 14 controls the address value to which write pointer logic 11 points. Similarly, read control 15 controls the address value to which read pointer logic 12 points. Reset logic 17 allows for the resetting of the write and read pointers.
Flag logic 16 generates flags to prevent reading of storage locations which do not contain valid data and to prevent writing into storage locations which contain data not yet consumed. Flag logic 16 include a pair of associated output lines labeled EF and FF. During operation, an empty flag signal is asserted by flag logic 16 and provided at the EF output line when memory 10 contains no unread data. Similarly, a full flag signal is provided at the FF output line when memory 10 is entirely filled with unread data.
When data is read from a particular location in memory 10, time is required to decode the address stored by write pointer logic 11 and to allow the data to propagate through the sense amplifier within memory 10 to three-state buffers 13. Time is also required for flag logic 16 to determine whether memory 10 is completely filled or completely empty and to thereby assert or deassert the full flag or the empty flag, respectively. It is desirable to minimize the time required to read data from a FIFO. It is further desirable to minimize the time required to generate the full flag and the empty flag.